{% extends "pages/base.html" %}
{% block title %}Home{% endblock %}
{% block content %}
Số phép so sánh tối thiểu cần sử dụng để tìm ra cả giá trị lớn nhất lẫn giá trị nhỏ nhất của một dãy gồm {N} phần tử là bao nhiêu? Ghi ra một số nguyên duy nhất là kết quả đáp án. ----------------------------------------------------------- Gợi ý phương pháp: Chia dãy thành hai nửa, tìm min và max mỗi nửa rồi so sánh chúng với nhau để tổng hợp kết quả. Xét mảng arr[lo..hi], mã giả để tìm min và max của mảng này như sau: Cho đồ thị hai phía $G=(X\cup Y, E)$ với $|X|=${m}, $|Y|=${n}, $|E|=${k}, và lực lượng cặp ghép lớn nhất của $G$ là {s}. Hãy tính lực lượng tập độc lập lớn nhất của $G$. Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho nhân viên chăm sóc khách hàng này. NP NP-khó NP-đầy đủ P Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm. Hỏi có tồn tại một hành trình cho nhân viên chăm sóc khách hàng này với chi phí không quá \(k\) hay không? NP NP-khó NP-đầy đủ P Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của một khách hàng để bảo trì sản phẩm của công ty và quay trở lại công ty mình sau khi xong việc. Có \(n\) vị trí trong thành phố 1,2,..,\(n\), địa điểm công ty là vị trí số 1 và địa điểm khách hàng là vị trí số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) vị trí này. NP NP-khó NP-đầy đủ P Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho thương nhân đó. NP NP-khó NP-đầy đủ P Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hỏi có tồn tại một hành trình cho thương nhân này có chi phí không quá \(k\) hay không? NP NP-khó NP-đầy đủ P Một thương nhân ở thành phố A muốn tìm hiểu thị trường ở thành phố B. Có \(n\) thành phố 1,2,..,\(n\), thành phố A ở thành phố số 1 và thành phố B là thành phố số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) thành phố. Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho thương nhân này đi từ thành phố A đến thành phố B và quay trở về thành phố B sau khi xong việc. Hành trình có thể đi qua các thành phố trung gian trong số \(n\) thành phố. Lớp bài toán nào là chính xác nhất cho bài toán trên? NP NP-khó NP-đầy đủ P Thuật toán Bellman-Ford tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây? Đồ thị tổng quát Đồ thị không chứa chu trình âm Đồ thị không có cạnh trọng số âm Đồ thị có hướng không có chu trình DAG Cây Đồ thị hai phía O(1) O(n) O(nlogn) O(logn) Không đáp án nào đúng Trong các thuật toán dưới đây, thuật toán nào không phải là thuật toán chia
để trị? Sắp xếp nhanh Sắp xếp trộn Tìm kiếm nhị phân O(logn) O(n) O(nlogn) O(1) O(log(logn)) Không đáp án nào đúng Xét đa thức p(x) = a0 + a1*x + a2*x2 + a3*x3, trong đó ai! = 0, với mọi i. Số phép nhân tối thiểu cần thiết để tính giá trị của p(x) với đầu vào x bất kỳ? 3 4 6 9 12 Đáp án khác Điều nào sau đây là đúng về độ phức tạp thuật toán là nghiệm của hệ thức truy hồi T(n)=2T(n/2) + logn với T (1) = 1? O(n) O(nlogn) O(logn) O(n2) Không đáp án nào đúng Cho mảng gồm các phần tử sau, 23, 32, 45, 69, 72, 73, 89, 97. Thuật toán sắp xếp nào dưới đây sử dụng ít phép so sánh nhất để sắp xếp mảng tăng dần? Merge sort Quick sort sử dụng phần tử cuối cùng là phần tử pivot Thuật toán dưới đây có chức năng gì? Tính tổng x+y Tính phần dư của x chia cho y Tìm bội số chung nhỏ nhất của x và y Không đáp án nào đúng Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a. Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu? 3 4 5 6 Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó. Cho dãy số 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2 . Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu? 7 14 20 18 Đáp án khác Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó. Cho dãy số 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2 . Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu? 7 14 20 18 Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó. Cho dãy số 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu? 7 17 21 27 Đáp án khác Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó. Cho dãy số 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu? 7 17 21 27 Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 2, 5, 8, 6, 3, 4, 10, 14, 8. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu? 30 31 32 33 34 Đáp án khác Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 2, 5, 8, 6, 3, 4, 10, 14, 8. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu? 30 31 32 33 34 Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 6, 4, 9, 2, 5, 9, 10, 14, 6. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu? 36 37 38 40 42 Đáp án khác Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 6, 4, 9, 2, 5, 9, 10, 14, 6. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu? 36 37 38 40 42 Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. 9 phần tử 1,2…, 9 có trọng số tương ứng là 2, 6, 8, 1, 7, 4, 10, 4, 5. Hãy chọn ra tập con S các phần tử i[1] < i[2] < … < i[k] từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử i[j] và i[j+1] lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= i[j+1] – i[j] <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con lớn nhất). Hỏi tổng trọng số các phần tử của S là bao nhiêu? 30 32 34 35 Đáp án khác Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. 9 phần tử 1,2…, 9 có trọng số tương ứng là 2, 6, 8, 1, 7, 4, 10, 4, 5. Hãy chọn ra tập con S các phần tử i[1] < i[2] < … < i[k] từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử i[j] và i[j+1] lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= i[j+1] – i[j] <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con lớn nhất). Hỏi tổng trọng số các phần tử của S là bao nhiêu? 30 32 34 35 Cấu trúc dữ liệu Deque cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau? vào một đầu, ra đầu còn lại vào và ra được từ cả hai đầu vào và ra duy nhất một đầu không cách nào trong các cách ở đây Đáp án khác Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v] Kết luận nào sau đây đúng? low[7] = 4 và num[7] = 7 low[7] = 7 và num[7] = 7 low[7] = 6 và num[7] = 7 low[7] = 5 và num[7] = 7 low[7] = 3 và num[7] = 5 Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v] Kết luận nào sau đây đúng? low[7] = 4 và num[7] = 7 low[7] = 7 và num[7] = 7 low[7] = 6 và num[7] = 7 low[7] = 5 và num[7] = 7 low[7] = 3 và num[7] = 5 Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v] Kết luận nào sau đây đúng? low[6] = 2, num[6] = 5 low[6] = 3, num[6] = 5 low[6] = 5, num[6] = 5 low[6] = 4, num[6] = 5 low[6] = 4, num[6] = 6 Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1,2,3,4,5,6,7,8,9} và tập cạnh E = {(1, 3),(1, 8),(1, 9),(2, 3),(2, 4),(2, 6),(3, 5),(4, 6),(4, 7),(5, 6),(5, 7),(8, 9)}. Thực hiện thuật toán DFS của Tarjan (các đỉnh được duyệt theo thứ tự từ điển) tìm low và num của mỗi đỉnh, trong đó: num[v] là số thứ tự đỉnh v được thăm low[v] được định nghĩa như sau: nếu tồn tại cạnh ngược (y,x) trong đó y là con cháu của v và x là tổ tiên của v thì low[v] bằng giá trị nhỏ nhất của num[x] (trong số các đỉnh x đó). Ngược lại, nếu không tồn tại cạnh ngược (y,x) như vậy thì low[v] = num[v] Kết luận nào sau đây đúng? low[6] = 2, num[6] = 5 low[6] = 3, num[6] = 5 low[6] = 5, num[6] = 5 low[6] = 4, num[6] = 5 low[6] = 4, num[6] = 6 Thuật toán Dijkstra tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây? Đồ thị tổng quát Đồ thị không chứa chu trình âm Đồ thị không có cạnh trọng số âm Đồ thị có hướng không có chu trình DAG Cây Đồ thị hai phía Một thuật toán duyệt toàn bộ được gọi là hiệu quả: khi có độ phức tạp tính toán là hàm mũ khi có độ phức tạp tính toán là đa thức khi có độ phức tạp tính toán là hằng số khi có độ phức tạp khấu trừ là tuyến tính khi có độ phức tạp khấu trừ là hằng số khi có độ phức tạp khấu trừ là đa thức Không mệnh đề nào trong các mệnh đề ở đây thoả mãn Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất là O\((n^2\)) và trong tình huống tốt nhất là O(n) Độ phức tạp trong tình huống tồi nhất là O(\(n^2\)) và tình huống tốt nhất là O(nlogn) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(n^2\)) Độ phức tạp trong tình huống tồi nhất và tốt nhất đều là O(\(nlogn\)) Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau: Đổ nước vào đầy bình 1 Đổ nước vào đầy bình 2 Đổ hết nước từ bình 1 ra ngoài Đổ hết nước từ bình 2 ra ngoài Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng) Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng) Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau: B1: Đổ nước vào đầy bình 1 B2: Đổ nước từ bình 1 sang bình 2 B3: Đổ nước vào đầy bình 1 B4: Đổ nước từ bình 1 sang bình 2 ta sẽ thu được 4 lít nước ở bình 1. Với a = 10, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu? 3 4 6 Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau: Đổ nước vào đầy bình 1 Đổ nước vào đầy bình 2 Đổ hết nước từ bình 1 ra ngoài Đổ hết nước từ bình 2 ra ngoài Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng) Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng) Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau: B1: Đổ nước vào đầy bình 1 B2: Đổ nước từ bình 1 sang bình 2 B3: Đổ nước vào đầy bình 1 B4: Đổ nước từ bình 1 sang bình 2 ta sẽ thu được 4 lít nước ở bình 1. Với a = 7, b = 5, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 3 lít ở 1 trong 2 bình là bao nhiêu? 4 5 6 Không có phương án nào thực hiện được Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau: Đổ nước vào đầy bình 1 Đổ nước vào đầy bình 2 Đổ hết nước từ bình 1 ra ngoài Đổ hết nước từ bình 2 ra ngoài Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng) Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng) Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau: B1: Đổ nước vào đầy bình 1 B2: Đổ nước từ bình 1 sang bình 2 B3: Đổ nước vào đầy bình 1 B4: Đổ nước từ bình 1 sang bình 2 ta sẽ thu được 4 lít nước ở bình 1. Với a = 3, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu? 2 3 4 5 Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau: Đổ nước vào đầy bình 1 Đổ nước vào đầy bình 2 Đổ hết nước từ bình 1 ra ngoài Đổ hết nước từ bình 2 ra ngoài Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng) Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng) Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau: B1: Đổ nước vào đầy bình 1 B2: Đổ nước từ bình 1 sang bình 2 B3: Đổ nước vào đầy bình 1 B4: Đổ nước từ bình 1 sang bình 2 ta sẽ thu được 4 lít nước ở bình 1. Với a = 2, b = 9, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 5 lít ở 1 trong 2 bình là bao nhiêu? 3 4 5 Không có phương án thực hiện 5 2 9 4 Đáp án khác 5 2 9 4 5 7 6 4 Đáp án khác 5 7 6 4 4 3 2 5 Đáp án khác 4 3 2 5 5 3 4 6 Đáp án khác 5 3 4 6 1 4 6 5 Đáp án khác 1 4 6 5 1 4 6 7 Đáp án khác 1 4 6 7 1 5 2 7 Đáp án khác 1 5 2 7 4 5 3 7 Đáp án khác 4 5 3 7 Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Câu 0
Câu 4121026
Algorithm: minmax(lo, hi)
if hi – lo ≤ 1 then
return (max(arr[lo], arr[hi]), min((arr[lo], arr[hi]))
else
(max1, min1):= minmax(lo, ⌊((lo + hi)/2)⌋)
(max2, min2):= minmax(⌊((lo + hi)/2) + 1)⌋, hi)
return (max(max1, max2), min(min1, min2))
Đáp án: 100">
Câu 4092895
Đáp án: 100">
Câu 4092853
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
Đáp án: 100
[0]
[0]
Câu 4092854
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
[0]
Đáp án: 100
[0]
Câu 4092855
Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho nhân viên chăm sóc khách hàng này đến địa điểm khách hàng và quay trở về công ty sau khi xong việc. Hành trình có thể đi qua các vị trí trung gian.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
[0]
[0]
Đáp án: 100
Câu 4092856
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
Đáp án: 100
[0]
[0]
Câu 4092857
Lớp bài toán nào là chính xác nhất cho bài toán trên?
[0]
[0]
Đáp án: 100
[0]
Câu 4092858
[0]
[0]
[0]
Đáp án: 100
Câu 4092884
Đáp án: -50
Đáp án: 25
Đáp án: 25
Đáp án: 25
Đáp án: 25
Đáp án: -50
Câu 4121027
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4121028
Đáp án: 50
[0]
[0]
[0]
Đáp án: 50
Câu 4121029
Đáp án: 100
[0]
[0]
[0]
[0]
[0]
Câu 4121030
Đáp án: 100
[0]
[0]
[0]
[0]
[0]
Câu 4121031
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4121032
[0]
Đáp án: 100
[0]
[0]
Câu 4121033

Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4149876
[0]
Đáp án: 100
[0]
[0]
Câu 4121035
[0]
[0]
[0]
Đáp án: 100
[0]
Câu 4149877
[0]
[0]
[0]
Đáp án: 100
Câu 4121036
[0]
[0]
Đáp án: 100
[0]
[0]
Câu 4149878
[0]
[0]
Đáp án: 100
[0]
Câu 4121037
[0]
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4149879
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4121038
[0]
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149880
[0]
[0]
Đáp án: 100
[0]
[0]
Câu 4121039
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149881
[0]
Đáp án: 100
[0]
[0]
Câu 4121040
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149813
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4092802
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4149814
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4092803
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4092885
Đáp án: -50
Đáp án: -25
Đáp án: 50
Đáp án: -25
Đáp án: 50
Đáp án: -25
Câu 4121041
[0]
[0]
Đáp án: 50
[0]
Đáp án: 50
[0]
[0]
Câu 4149820
Phát biểu nào sau đây đúng với thuật toán sắp xếp nổi bọt cho dãy gồm n phần tử
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4092809
Phát biểu nào sau đây đúng với thuật toán sắp xếp nổi bọt cho dãy gồm n phần tử
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149821
Phát biểu nào sau đây đúng với thuật toán sắp xếp chèn cho dãy gồm n phần tử
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4092810
Phát biểu nào sau đây đúng với thuật toán sắp xếp chèn cho dãy gồm n phần tử
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149822
Phát biểu nào sau đây đúng với thuật toán sắp xếp trộn cho dãy gồm n phần tử
[0]
[0]
[0]
[0]
Đáp án: 100
Câu 4092811
Phát biểu nào sau đây đúng với thuật toán sắp xếp trộn cho dãy gồm n phần tử
[0]
[0]
[0]
[0]
Đáp án: 100
Câu 4149823
Phát biểu nào sau đây đúng với thuật toán sắp xếp vun đống cho dãy gồm n phần tử
[0]
[0]
[0]
[0]
Đáp án: 100
Câu 4092812
Phát biểu nào sau đây đúng với thuật toán sắp xếp vun đống cho dãy gồm n phần tử
[0]
[0]
[0]
[0]
Đáp án: 100
Câu 4149824
Phát biểu nào sau đây đúng với thuật toán sắp xếp lựa chọn cho dãy gồm n phần tử
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4092813
Phát biểu nào sau đây đúng với thuật toán sắp xếp lựa chọn cho dãy gồm n phần tử
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4092878
[0]
Đáp án: 100
[0]
Câu 4092879
Đáp án: 100
[0]
[0]
[0]
Câu 4092880
[0]
[0]
Đáp án: 100
[0]
Câu 4092881
[0]
Đáp án: 100
[0]
[0]
Câu 4121042
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
S.PUSH(i);
}
for i = 1 to 4 do {
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4149830
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
S.PUSH(i);
}
for i = 1 to 4 do {
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
[0]
[0]
[0]
Câu 4121043
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
S.PUSH(i);
}
for i = 1 to 3 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149831
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
S.PUSH(i);
}
for i = 1 to 3 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
Đáp án: 100
[0]
[0]
Câu 4121044
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 5 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149832
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 5 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
[0]
Đáp án: 100
[0]
[0]
Câu 4121045
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 7 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
[0]
[0]
[0]
[0]
Câu 4149833
Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 7 do{
S.PUSH(i);
}
for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);
Đáp án: 100
[0]
[0]
[0]
Câu 4121046
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
[0]
[0]
Đáp án: 100
[0]
Câu 4149834
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
[0]
[0]
Đáp án: 100
Câu 4121047
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 3 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
[0]
[0]
Đáp án: 100
[0]
Câu 4149835
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 3 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
[0]
[0]
Đáp án: 100
Câu 4121048
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 2 to 10 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
Đáp án: 100
[0]
[0]
[0]
Câu 4149836
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 2 to 10 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
Đáp án: 100
[0]
[0]
Câu 4121049
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
[0]
[0]
Đáp án: 100
[0]
Câu 4149837
Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 10 downto 1 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);
[0]
[0]
[0]
Đáp án: 100
Câu 4092827
Xét thuật toán tham lam sau:
Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=19\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=15\)
\(C_1=16, C_2=8, C_3 =20, W_1=6, W_2=10, W_3=13\)
\(C_1=16, C_2=8, C_3 =20, W_1=7, W_2=10, W_3=14\)
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=14\)
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=11\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
\(C_1=15, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
\(C_1=16, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
\(C_1=15, C_2=27, C_3 =13, W_1=5, W_2=10, W_3=6\)
\(C_1=14, C_2=27, C_3 =12, W_1=5, W_2=10, W_3=6\)
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=7\)
\(S_1=5, S_2=2, S_3 =6, F_1=7, F_2=5, F_3=15\)
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=6\)
\(S_1=1, S_2=6, S_3 =5, F_1=5, F_2=10, F_3=7\)
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=4\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=2\)
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=3\)
\(C_1=8, C_2=15, C_3=8, W_1=3, W_2=4, W_3=1\)
\(C_1=8, C_2=10, C_3=8, W_1=2, W_2=4, W_3=3\)
Có \(n=9\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =4, F_8=6, S_9 =6, F_9=8\)
\(S_1=2, F_1=4, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =6, F_4=8, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
50
60
70
80
90
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
40
50
60
70
80
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
10
20
30
40
50
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
137
100
37
52
Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
137
100
37
52
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
137
100
37
52
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
37
103
11
42
Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
37
103
11
42
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
37
103
11
42
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
30
3
6
8
Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
30
3
6
8
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}
30
3
6
8
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}
20
4
5
9
Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}
20
4
5
9
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}
20
4
5
9
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
10
4
6
7
Đáp án khác
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
10
4
6
7
Hỏi kết quả của chương trình sau
#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}
10
4
6
7
Phát biểu nào sau đây không đúng
Các phần tử của danh sách liên kết luôn được cấp phát kế tiếp nhau trong bộ nhớ
Các phần tử của danh sách liên kết không nhất thiết được cấp phát kế tiếp nhau trong bộ nhớ
Không đáp án nào đúng
Phát biểu ”Ta truy nhập đến các phần tử của danh sách liên kết thông qua chỉ số” là đúng hay sai?
Đúng
Sai
Phát biểu ”Thao tác tìm kiếm một phần tử trên danh sách liên kết có độ phức tạp trong tình huống tồi nhất là O(n) với n là số phần tử của danh sách liên kết” là đúng hay sai?
Đúng
Sai
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 3 có kề nhau hay không?
Có
Không
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 3 có kề nhau hay không?
Có
Không
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 3 có kề nhau hay không?
Có
Không
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 3 có kề nhau hay không?
Có
Không
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 4 có kề nhau hay không?
Có
Không
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 2 và 4 có kề nhau hay không?
Có
Không
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 4 có kề nhau hay không?
Có
Không
Cho đồ thị vô hướng \(G\) với tập đỉnh\( V = \{1,2,3,4\}\) được biểu diễn bởi ma trận kề sau đây
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Hỏi hai đỉnh 1 và 4 có kề nhau hay không?
Có
Không
Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?
Đúng
Sai
Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?
Đúng
Sai
Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?
Đúng
Sai
Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}
Sắp xếp chèn
Sắp xếp lựa chọn
Sắp xếp nổi bọt
Sắp xếp vun đống
Đáp án khác
Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}
Sắp xếp chèn
Sắp xếp lựa chọn
Sắp xếp nổi bọt
Sắp xếp vun đống
Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}
Sắp xếp chèn
Sắp xếp lựa chọn
Sắp xếp nổi bọt
Sắp xếp vun đống
Trong các kỹ năng cơ bản dưới đây, kỹ năng nào cần rèn luyện trong khoá học?
Kỹ năng đọc đề
Kỹ năng phân loại bài toán
Kỹ năng kiểm thử chương trình
Kỹ năng phân tích thuật toán
Tất cả các kỹ năng ở đây
Given a sequence \(a = a_1, a_2, …, a_n\). The subsequence of a is defined as the sequence obtained by removing some elements of a.
Given the sequence a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 and b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. You are asked to compute the length of the longest subsequence (i.e. the maximum number of elements) that is both a subsequence of a and a subsequence of b.
3
4
5
6
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 5, 2, 3, 7, 2, 3, 6, 3. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
26
27
28
29
30
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 7, 1, 4, 2, 7, 6, 5, 3, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
24
25
26
27
28
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 3, 1, 2, 6, 4, 3, 1, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
16
18
19
23
Giả sử độ phức tạp tính toán của giải thuật chia để trị khi giải một bài toán kích thước n có công thức truy hồi như sau:
$$ T(n) = 9 T(n/3) + n^2 $$
Dùng định lý thợ (master theorem), hãy xác định độ phức tạp tính toán của giải thuật trong trường hợp trên.
\(\Theta(n^2logn) \)
\(\Theta(nlogn) \)
\(\Theta(n^2) \)
\(\Theta(nlog^2n) \)
Đáp án khác
30
31
32
33
34
Given 9 elements 1, 2, …, 9 lying on a line, where the element i is at the coordinate i. The elements 1,2…, 9 have weight 6, 4, 9, 2, 5, 9, 10, 14, 6 respectively. You are asked to choose a subsequence S of element i1 < i2 < … < ik from these 9 elements such that the distance between 2 elements ij and ij+1 (j = 1, ..., k-1) is greater than or equal to 2 and is smaller or equal to 4 (2 <= ij+1 – ij <= 4) and the sum of the weight of these elements is maximum. What is this sum?
36
37
38
40
42
Given 9 elements 1, 2, …, 9 lying on a line, where the element i is at the coordinate i. The elements 1,2…, 9 have weight 2, 6, 8, 1, 7, 4, 10, 4, 5 respectively. You are asked to choose a subsequence S of element i1 < i2 < … < ik from these 9 elements such that the distance between 2 elements ij and ij+1 (j = 1, ..., k-1) is greater than or equal to 2 and is smaller or equal to 4 (2 <= ij+1 – ij <= 4) and the sum of the weight of these elements is maximum. What is this sum?
30
32
34
35
Given the sequence a = a[1], a[2], …, a[n]. A subsequence of a is defined as a sequence a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), whose weight is the sum of its elements.
Given the sequence 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. You are asked to compute the weight of the subsequence with the maximum weight.
7
17
21
27
Given the sequence a = a[1], a[2], …, a[n]. A subsequence of a is defined as a sequence a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), whose weight is the sum of its elements.
Given the sequence 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. You are asked to compute the weight of the subsequence with the maximum weight.
7
14
20
18
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
1,2,3,4,5
1,2,5,3,4
1,3,4,2,5
1,4,3,2,5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
1,2,3,4,5
1,2,5,3,4
1,3,4,2,5
1,4,3,2,5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
2,1,5,3,4
2,1,3,4,5
2, 3, 4, 1, 5
2, 5, 4, 1, 3
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
2,1,5,3,4
2,1,3,4,5
2, 3, 4, 1, 5
2, 5, 4, 1, 3
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
3, 1, 2, 4, 5
3, 2, 4, 1, 5
3, 2, 4, 5, 1
3, 5, 4, 2, 1
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
3, 1, 2, 4, 5
3, 2, 4, 1, 5
3, 2, 4, 5, 1
3, 5, 4, 2, 1
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
4, 1, 2, 3, 5
4, 5, 1, 2, 3
4, 3, 2, 1, 5
4, 3, 2, 5, 1
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
4, 1, 2, 3, 5
4, 5, 1, 2, 3
4, 3, 2, 1, 5
4, 3, 2, 5, 1
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
5, 1, 2, 3, 4
5, 2, 1, 4, 3
5, 3, 4, 1, 2
5, 4, 3, 2, 1
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều rộng bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
5, 1, 2, 3, 4
5, 2, 1, 4, 3
5, 3, 4, 1, 2
5, 4, 3, 2, 1
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
1,2,3,4,5
1,2,5,3,4
1,3,4,2,5
1,4,3,2,5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 1 thì thứ tự các đỉnh được duyệt là thế nào sau đây
1,2,3,4,5
1,2,5,3,4
1,3,4,2,5
1,4,3,2,5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
2, 3, 4, 5, 1
2, 1, 5, 3, 4
2, 3, 4, 5, 1
2, 1, 3, 4, 5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 2 thì thứ tự các đỉnh được duyệt là thế nào sau đây
2, 3, 4, 5, 1
2, 1, 5, 3, 4
2, 3, 4, 5, 1
2, 1, 3, 4, 5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
3, 2, 4, 5, 1
3, 2, 1, 5, 4
3, 2, 4, 1, 5
3, 1, 2, 4, 5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 3 thì thứ tự các đỉnh được duyệt là thế nào sau đây
3, 2, 4, 5, 1
3, 2, 1, 5, 4
3, 2, 4, 1, 5
3, 1, 2, 4, 5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
4, 2, 3, 5, 1
4, 2, 1, 5, 3
4, 3, 2, 5, 1
4, 1, 2, 3, 5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 4 thì thứ tự các đỉnh được duyệt là thế nào sau đây
4, 2, 3, 5, 1
4, 2, 1, 5, 3
4, 3, 2, 5, 1
4, 1, 2, 3, 5
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
5, 4, 3, 2, 1
5, 1, 2, 4, 3
5, 3, 4, 2, 1
5, 1, 3, 4, 2
Cho đồ thị vô hướng \(G=(V,E)\) trong đó \(V=\{1,2,3,4,5\}\) là tập đỉnh và tập cạnh \(E=\{(1,2),(1,5),(2,3),(2,4),(3,4)\}\). Hỏi khi duyệt \(G\) theo chiều sâu bắt đầu từ đỉnh 5 thì thứ tự các đỉnh được duyệt là thế nào sau đây
5, 4, 3, 2, 1
5, 1, 2, 4, 3
5, 3, 4, 2, 1
5, 1, 3, 4, 2
Cho dãy 1, 4, 3, 6, 7, 2, 5 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 4, 6, 2, 3, 5, 1
1, 2, 3, 4, 5, 6, 7
2, 1, 4, 3, 6, 7, 5
5, 3, 1, 7, 6, 2, 4
Cho dãy 1, 4, 3, 6, 7, 2, 5 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 4, 6, 2, 3, 5, 1
1, 2, 3, 4, 5, 6, 7
2, 1, 4, 3, 6, 7, 5
5, 3, 1, 7, 6, 2, 4
Cho dãy 1, 4, 8, 6, 3, 5, 2 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
1, 2, 3, 4, 5, 8, 6
1, 2, 4, 3, 6, 8, 5
8, 4, 6, 2, 3, 5, 1
3, 5, 1, 8, 6, 2, 4
Cho dãy 1, 4, 8, 6, 3, 5, 2 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống. Trong các dãy sau đây, dãy nào tương ứng với max-heap?
1, 2, 3, 4, 5, 8, 6
1, 2, 4, 3, 6, 8, 5
8, 4, 6, 2, 3, 5, 1
3, 5, 1, 8, 6, 2, 4
Cho dãy 2, 4, 8, 6, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 2, 3, 4, 5, 8, 6
7, 2, 4, 3, 6, 8, 5
8, 5, 7, 2, 3, 4, 6
3, 5, 7, 8, 4, 2, 6
Cho dãy 2, 4, 8, 6, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 2, 3, 4, 5, 8, 6
7, 2, 4, 3, 6, 8, 5
8, 5, 7, 2, 3, 4, 6
3, 5, 7, 8, 4, 2, 6
Cho dãy 2, 4, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 2, 3, 4, 5, 8, 1
8, 2, 4, 3, 1, 7, 5
8, 5, 7, 2, 3, 4, 1
3, 5, 7, 8, 4, 2, 1
Cho dãy 2, 4, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 2, 3, 4, 5, 8, 1
8, 2, 4, 3, 1, 7, 5
8, 5, 7, 2, 3, 4, 1
3, 5, 7, 8, 4, 2, 1
Cho dãy 2, 6, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 2, 3, 6, 5, 8, 1
8, 2, 6, 3, 1, 7, 5
3, 5, 7, 8, 6, 2, 1
8, 5, 7, 2, 3, 6, 1
Cho dãy 2, 6, 8, 1, 3, 5, 7 cần được sắp xếp theo thứ tự không giảm bằng thuật toán sắp xếp vun đống (Heap Sort). Trong các dãy sau đây, dãy nào tương ứng với max-heap?
7, 2, 3, 6, 5, 8, 1
8, 2, 6, 3, 1, 7, 5
3, 5, 7, 8, 6, 2, 1
8, 5, 7, 2, 3, 6, 1
Trong các mục tiêu dưới đây, đâu là mục tiêu chính của môn học Thuật toán ứng dụng? (Có thể trả lời nhiều đáp án)
Tăng cường khả năng mô hình hoá bài toán thực tế
Tăng cường kỹ năng đề xuất Cấu trúc dữ liệu và Thuật toán cho các bài toán thực tế
Tăng cường kỹ năng chuyển hoá thiết kế Cấu trúc dữ liệu và Thuật toán sang
chương trình có thể chạy được và đúng
Tăng cường kỹ năng lập trình ngôn ngữ
Tăng cường kỹ năng phân tích, thiết kế các hệ thống thông tin lớn
Kết luận nào sau đây đúng với hàng đợi?
Phần tử nào được đưa vào hàng đợi đầu tiên thì sẽ được lấy ra cuối cùng.
Phần từ nào đưa vào hàng đợi cuối cùng thì sẽ được lấy ra cuối cùng.
Kết luận nào sau đây đúng với hàng đợi?
Hàng đợi là cấu trúc tuyến tính
Hàng đợi là cấu trúc phân cấp, dạng cây
Kết luận nào sau đây đúng với hàng đợi?
Phần tử nào được đưa vào hàng đợi đầu tiên thì sẽ được lấy ra cuối cùng.
Phần từ nào đưa vào hàng đợi cuối cùng thì sẽ được lấy ra cuối cùng.
Kết luận nào sau đây đúng với hàng đợi?
Hàng đợi là cấu trúc tuyến tính
Hàng đợi là cấu trúc phân cấp, dạng cây
Kết luận nào sau đây đúng với ngăn xếp?
Phần tử nào được đưa vào ngăn xếp đầu tiên thì sẽ được lấy ra cuối cùng.
Phần từ nào đưa vào ngăn xếp cuối cùng thì sẽ được lấy ra cuối cùng.
Kết luận nào sau đây đúng với ngăn xếp?
Ngăn xếp là cấu trúc tuyến tính
Ngăn xếp là cấu trúc phân cấp, dạng cây.
Kết luận nào sau đây đúng với ngăn xếp?
Phần tử nào được đưa vào ngăn xếp đầu tiên thì sẽ được lấy ra cuối cùng.
Phần từ nào đưa vào ngăn xếp cuối cùng thì sẽ được lấy ra cuối cùng.
Kết luận nào sau đây đúng với ngăn xếp?
Ngăn xếp là cấu trúc tuyến tính
Ngăn xếp là cấu trúc phân cấp, dạng cây.
Giả sử cho trước hàm sau:
int partition (int a[], int n);
Hàm này lấy phần tử đầu tiên của mảng a[] làm phần tử chốt, sau đó sắp xếp các phần tử nhỏ hơn hoặc bằng phần từ chốt về phần bên trái của mảng, và tất cả phần tử lớn hơn phần tử chốt về phần bên phải của mảng. Ngoài ra, hàm cũng di chuyển phần tử chốt về vị trí cuối cùng của phần bên trái. Hàm trả về số lượng phần tử của phần bên trái.
Đoạn chương trình C bị khuyết sau sử dụng hàm partition function để tìm phần tử nhỏ thứ k trong mảng a[] kích thước n (giả định k ≤ n). Hãy lựa chọn phần danh sách tham số đúng trong các phương án dưới đây để điền vào chỗ trống.
int kth_smallest (int a[], int n, int k) {
int left_end = partition (a, n);
if (left_end+1==k){
return a [left_end];
}
if (left_end+1 > k) {
return kth_smallest (____________________);
}
else {
return kth_smallest (____________________);
}
}(a, left_end, k) và (a+left_end+1, n–left_end–1, k–left_end–1)
(a, left_end, k) và (a, n–left_end–1, k–left_end–1)
(a, left_end+1, N–left_end–1, K–left_end–1) và (a, left_end, k)
(a, n–left_end–1, k–left_end–1) và (a, left_end, k)
Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
i = 1;
While s <= n {
s = s * 2;
i++;
}
}
\(O(logn)\)
\(O(n)\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = a + 1;
i = i + 1;
}
}
\(O(logn)\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = 2*a;
i++;
}
}
\(O(logn)\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
a = 2;
i = 1;
While s <= n {
s = s * a;
a = a*a;
i = i + 1;
}
}
\(O(log(logn))\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
If (n <= 1 ) return 0;
If n mod 2 = 0 {
Return 4*f(n/2) + 3n - 2;
}else{
Return 2*f(n/2) + 2n + 5;
}
}
\(O(log(logn))\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(logn)\)
Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )
f(n){
k = 1;
for i = 1 to n do{
While k <= n and a[k] < a[i] do{
k = k + 1;
}
}
}
\(O(nlogn)\)
\(O(n)\)
\(O(n^2)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
i = 1;
While s <= n {
s = s * 2;
i++;
}
}
\(O(logn)\)
\(O(n)\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = a + 1;
i = i + 1;
}
}
\(O(logn)\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = 2*a;
i++;
}
}
\(O(logn)\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
a = 2;
i = 1;
While s <= n {
s = s * a;
a = a*a;
i = i + 1;
}
}
\(O(log(logn))\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
If (n <= 1 ) return 0;
If n mod 2 = 0 {
Return 4*f(n/2) + 3n - 2;
}else{
Return 2*f(n/2) + 2n + 5;
}
}
\(O(log(logn))\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(logn)\)
Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )
f(n){
k = 1;
for i = 1 to n do{
While k <= n and a[k] < a[i] do{
k = k + 1;
}
}
}
\(O(nlogn)\)
\(O(n)\)
\(O(n^2)\)
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
i = 1;
While s <= n {
s = s * 2;
i++;
}
}
\(O(logn)\)
\(O(n)\)
\(O(nlogn)\)
Đáp án khác
Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )
f(n){
k = 1;
for i = 1 to n do{
While k <= n and a[k] < a[i] do{
k = k + 1;
}
}
}
\(O(nlogn)\)
\(O(n)\)
\(O(n^2)\)
Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
If (n <= 1 ) return 0;
If n mod 2 = 0 {
Return 4*f(n/2) + 3n - 2;
}else{
Return 2*f(n/2) + 2n + 5;
}
}
\(O(log(logn))\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(logn)\)
Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 1;
a = 2;
i = 1;
While s <= n {
s = s * a;
a = a*a;
i = i + 1;
}
}
\(O(log(logn))\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = 2*a;
i++;
}
}
\(O(logn)\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Đáp án khác
Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){
s = 0;
a = 1;
i = 1;
While s <= n {
s = s + a;
a = a + 1;
i = i + 1;
}
}
\(O(logn)\)
\(O(n)\)
\(O(n^\frac {1}{2})\)
\(O(nlogn)\)
Đáp án khác
Những mệnh đề nào sau đây là ĐÚNG?
Nếu \(A \in NP\)-khó và \(A\prec B\), thì \(B \in NP\)-khó
Nếu \(A \in NP\)-khó và \(B\prec A\), thì \(B \in NP\)-khó
Nếu \(A \in P\) và \(A\prec B\), thì \(B \in P\)
Nếu \(A \in P\) và \(B\prec A\), thì \(B \in P\)
Thuật toán chia để trị thường được lập trình theo phương pháp nào sau đây?
Đệ quy
Dùng các vòng lặp
Quay lui
Dùng cú pháp lambda
Đáp án khác
Những phương pháp nào thường được sử dụng để đưa ra lời giải chấp nhận được mà không đảm bảo tính tối ưu trong thời gian đa thức cho bài toán thuộc lớp NP-khó?
Nhánh cận
Tham lam
Chia để trị
Qui hoạch động
Heuristic
Meta-heuristic
Học tăng cường
Thuật toán xấp xỉ
Tất cả các phương pháp liệt kê ở đây
Trong những nhận định dưới đây về thuật toán chia để trị và quy hoạch động, nhận định nào đúng? (có thể chọn nhiều đáp án)
Chia để trị thường được cài đặt bằng kỹ thuật đệ quy
Quy hoạch động có thể được cài đặt bằng vòng lặp
Trong quá trình giải bài toán, cả chia để trị và quy hoạch động đều cho độ phức tạp thuật toán trong thời gian đa thức
Chia để trị chia bài toán lớn thành các bài toán con độc lập, trong khi đó quy hoạch động thì chia bài toán lớn thành các bài toán con gối nhau
Đại dịch COVID19 diễn ra phức tạp trên toàn thế giới. Việt Nam cũng không phải là ngoại lệ. Rất nhiều người đã bị chết vì dịch bệnh. Công ty phân tích dữ liệu XTEC muốn thống kê số lượng người chết theo các độ tuổi: nhỏ hơn 15, từ 15 tới 20, từ 20 tới 40, từ 40 tới 60 và trên 60. Yêu cầu, cho trước một danh sách người chết vì dịch bệnh và độ tuổi của những người này, hãy đưa ra số lượng người chết theo các độ tuổi trên.
Bài toán này thuộc dạng bài nào trong các dạng bài sau:
Adhoc
Chia để trị
Quy hoạch động
Thuật toán đặc thù
Thuật toán trên đồ thị
Đáp án khác
Để giải nhanh và chính xác phương trình x3 + 2021x + 2 = 0 với -1000 ≤x ≤ 1000 với sai số chấp nhận được 10-6, chúng ta sử dụng phương pháp giải nào dưới đây?
Duyệt toàn bộ
Chia để trị
Quy hoạch động
Thuật toán đặc thù
Thuật toán trên đồ thị
Đáp án khác
Phương pháp Qui hoạch động trên Bitmask giải bài toán người du lịch cho lời giải thế nào?
Lời giải chấp nhận được (không đảm bảo tính tối ưu)
Lời giải tối ưu
Đáp án khác
Cấu trúc dữ liệu Queue cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?
vào một đầu, ra đầu còn lại
vào và ra được từ cả hai đầu
vào và ra duy nhất một đầu
không cách nào trong các cách ở đây
đáp án khác
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \(10n^2, nlogn, 1000\sqrt {n}\)
\(1000\sqrt {n}\), \(nlogn\), \(10n^2\)
\(nlogn\), \(1000\sqrt {n}\), \(10n^2\)
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \(10n^2, nlogn, 1000\sqrt {n}\)
\(1000\sqrt {n}\), \(nlogn\), \(10n^2\)
\(nlogn\), \(1000\sqrt {n}\), \(10n^2\)
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^4n, n^2, nlogn, 1000\sqrt {n}, log(logn)\)
\(1000\sqrt {n}\), \(log(logn)\), \(nlogn\), \(10^4n,n^2\)
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(n^2\), \(10^4n\)
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(10^4n,n^2\)
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^6n, n^3, \sqrt {nlogn}, \sqrt {n}, log(logn)\)
\(\sqrt {n}\), \(log(logn)\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(n^3\), \(10^6n\)
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^4n, n^2, nlogn, 1000\sqrt {n}, log(logn)\)
\(1000\sqrt {n}\), \(log(logn)\), \(nlogn\), \(10^4n,n^2\)
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(n^2\), \(10^4n\)
\(log(logn)\), \(1000\sqrt {n}\), \(nlogn\), \(10^4n,n^2\)
Sắp xếp các hàm sau đây theo thứ tự tăng dần của độ tăng: \( 10^6n, n^3, \sqrt {nlogn}, \sqrt {n}, log(logn)\)
\(\sqrt {n}\), \(log(logn)\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(n^3\), \(10^6n\)
\(log(logn)\), \(\sqrt {n}\), \(\sqrt {nlogn}\), \(10^6n\), \(n^3\)
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
3
4
6
9
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
4
5
8
10
Đáp án khác
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
4
5
8
10
Cấu trúc dữ liệu Stack cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?
vào một đầu, ra đầu còn lại
vào và ra được từ cả hai đầu
vào và ra duy nhất một đầu
không cách nào trong các cách ở đây
đáp án khác
Những thuật toán tham lam nào KHÔNG CHẮC CHẮN cho lời giải tối ưu bài toán tập đoạn thẳng không giao nhau?
Bắt đầu sớm xét trước
Kết thúc sớm xét trước
Ngắn hơn xét trước
Ít mâu thuẫn hơn xét trước
Given cubes (with their length, width and height) of 3 configurations: 3 x 2 x 3, 3 x 4 x 5 and 2 x 4 x 2. Assume the number of cubes in each configuration shape is infinite. What is the maximum height of the cubes that can be selected and arranged into a tower (the cubes can be rotated at different angles) such that the size of the upper cube a x b must be strictly smaller the size of the lower cube c x d, i.e. a < c and b < d
9
8
12
13
10
11
Given cubes (with their length, width and height) of 3 configurations: 3 x 2 x 3, 3 x 4 x 5 and 4 x 4 x 3. Assume the number of cubes in each configuration shape is infinite. What is the maximum height of the cubes that can be selected and arranged into a tower (the cubes can be rotated at different angles) such that the size of the upper cube a x b must be strictly smaller the size of the lower cube c x d, i.e. a < c and b < d
10
9
11
13
12
14
12
13
14
15
16
Bài toán người du lịch với yêu cầu tối thiểu hoá chi phí hành trình của người du lịch thuộc lớp bài toán nào?
NP
NP-khó
NP-đầy đủ
P
Những phương pháp nào có thể giải bài toán người du lịch cho lời giải chấp nhận được?
Nhánh cận
Tham lam
Qui hoạch động
Heuristic
Meta-heuristic
Học tăng cường
Tất cả các phương pháp trên
Những mối quan hệ nào sau đây là CHẮC CHẮN ĐÚNG?
\(P \subseteq NP\)
\(NPC \subseteq NP\)
\(P \subset NP\)
\(P \neq NP\)
\(P = NP\)
\(NPC = NP\)
\(NPC \subset NP\)
\(NPC \neq NP\)
\(NPC \subset NP\)-khó
\(NP\)-khó \(\cap NP = NPC\)
\(NP \subset NP\)-khó
\(P \neq NP\)-khó
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 2 x 4 x 2. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
9
8
12
13
10
11
Đáp án khác
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 2 x 4 x 2. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
9
8
12
13
10
11
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 4 x 4 x 3. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
10
9
11
13
12
14
Đáp án khác
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 4 x 4 x 3. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
10
9
11
13
12
14
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 8 và 3 x 3 x 5. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
12
13
14
15
16
Đáp án khác
Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 8 và 3 x 3 x 5. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d
12
13
14
15
16
Nếu công thức truy hồi độ phức tạp tính toán của phương pháp tìm kiếm nhị phân (binary search) được biểu diễn dưới dạng \(T(n)=aT(n/b)+O(n^d)\) thì giá trị \(a+b+d\) là bao nhiêu? Ghi ra một số nguyên duy nhất là kết quả đáp án.
Biết rằng hàm số f(x) = x19 - x2 - x + 1 có một nghiệm nằm trong khoảng [0, 1], bạn được yêu cầu lập trình để tìm và điền nghiệm trên với sai số 10-6 vào ô trống.
Có bao nhiêu cách chia 20 cái kẹo cho 9 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Có bao nhiêu cách chia 21 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà em nào cũng có kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?
(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)
Cho dãy số nguyên [-9, 17, -16, -50, 19, -26, 28, 8, 12, 14, -45, -5, 31, -23, 11, 41, 45, -8, -23, -14], hãy tìm một đoạn con các phần tử liên tiếp trong dãy sao cho tổng mũ 3 của các phần tử trong đoạn con là lớn nhất và điền giá trị tổng này vào ô trống
Có tồn tại thuật toán tham lam cho kết quả tối ưu với mọi bộ dữ liệu bài toán cái túi hay không?
Có
Không
Kết luận \(n^2-1000n+6=O(nlogn)\) là đúng hay sai
Yes
No
Kết luận \(n^2-1000n+6=O(nlogn)\) là đúng hay sai
Yes
No
Kết luận \(n^2-1000n+6=O(nlogn)\) là đúng hay sai
Yes
No
Thuật toán Người thu ngân có cho lời giải tối ư với các đồng tiền mệnh giá 1xu, 5xu, 10xu, 25xu và 100xu không?
Có
Không
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 4 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)1 --> 6 --> 4
1 --> 2 --> 5 --> 4
1 --> 3--> 2 --> 5 --> 4
1 --> 5 --> 4
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 6 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi độ dài đường đi (tính theo số lượng cạnh) từ đỉnh 6 đến đỉnh 3 là bao nhiêu?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)2
1
4
5
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6, 7} và tập cạnh E ={(1,2), (1,3), (2,4), (2,5), (3,5), (4,6), (4,7), (5, 6), (5, 7), (6, 7)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 6 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)1 --> 2 --> 4 --> 6
1 --> 3 --> 5 --> 7 --> 6
1 --> 3--> 5 --> 6
1 --> 5 --> 7 --> 6
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {a, b, c, d, e, f, g} và tập cạnh E ={(a,b), (a,c), (b,d), (b,e), (c,e), (d,f), (d,g), (e, f), (e, g), (f, g)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phải từ đỉnh a (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh a đến đỉnh f trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)a --> b --> d --> f
a --> c --> e --> g --> f
a --> c--> e --> f
a --> e --> g --> f
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh s (kí hiệu: BFS(s)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)




Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh b (kí hiệu: BFS(b)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.
(Lựa chọn sai sẽ bị trừ 25% số điểm của câu này)




Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
3
4
6
9
Đáp án khác
Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
4
5
8
10
Đáp án khác
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
Đáp án khác
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)
\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)
Đáp án khác
Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=7\)
\(S_1=5, S_2=2, S_3 =6, F_1=7, F_2=5, F_3=15\)
\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=6\)
\(S_1=1, S_2=6, S_3 =5, F_1=5, F_2=10, F_3=7\)
Đáp án khác
Có \(n=9\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =4, F_8=6, S_9 =6, F_9=8\)
\(S_1=2, F_1=4, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =6, F_4=8, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)
Đáp án khác
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=19\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=15\)
\(C_1=16, C_2=8, C_3 =20, W_1=6, W_2=10, W_3=13\)
\(C_1=16, C_2=8, C_3 =20, W_1=7, W_2=10, W_3=14\)
\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=14\)
Đáp án khác
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=11\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
\(C_1=15, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
\(C_1=16, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)
\(C_1=15, C_2=27, C_3 =13, W_1=5, W_2=10, W_3=6\)
\(C_1=14, C_2=27, C_3 =12, W_1=5, W_2=10, W_3=6\)
Đáp án khác
Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=4\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=2\)
\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=3\)
\(C_1=8, C_2=15, C_3=8, W_1=3, W_2=4, W_3=1\)
\(C_1=8, C_2=10, C_3=8, W_1=2, W_2=4, W_3=3\)
Đáp án khác
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
50
60
70
80
90
Đáp án khác
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
40
50
60
70
80
Đáp án khác
Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:
Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:
Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.
Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
10
20
30
40
50
Đáp án khác
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 5, 2, 3, 7, 2, 3, 6, 3. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
26
27
28
29
30
Đáp án khác
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 7, 1, 4, 2, 7, 6, 5, 3, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
24
25
26
27
28
Đáp án khác
Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 3, 1, 2, 6, 4, 3, 1, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
16
18
19
23
Đáp án khác
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho nhân viên chăm sóc khách hàng này.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
NP
NP-khó
NP-đầy đủ
P
Đáp án khác
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm. Hỏi có tồn tại một hành trình cho nhân viên chăm sóc khách hàng này với chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
NP
NP-khó
NP-đầy đủ
P
Đáp án khác
Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của một khách hàng để bảo trì sản phẩm của công ty và quay trở lại công ty mình sau khi xong việc. Có \(n\) vị trí trong thành phố 1,2,..,\(n\), địa điểm công ty là vị trí số 1 và địa điểm khách hàng là vị trí số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) vị trí này.
Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho nhân viên chăm sóc khách hàng này đến địa điểm khách hàng và quay trở về công ty sau khi xong việc. Hành trình có thể đi qua các vị trí trung gian.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
NP
NP-khó
NP-đầy đủ
P
Đáp án khác
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho thương nhân đó.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
NP
NP-khó
NP-đầy đủ
P
Đáp án khác
Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hỏi có tồn tại một hành trình cho thương nhân này có chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?
NP
NP-khó
NP-đầy đủ
P
Đáp án khác
Một thương nhân ở thành phố A muốn tìm hiểu thị trường ở thành phố B. Có \(n\) thành phố 1,2,..,\(n\), thành phố A ở thành phố số 1 và thành phố B là thành phố số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) thành phố. Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho thương nhân này đi từ thành phố A đến thành phố B và quay trở về thành phố B sau khi xong việc. Hành trình có thể đi qua các thành phố trung gian trong số \(n\) thành phố.
Lớp bài toán nào là chính xác nhất cho bài toán trên?
NP
NP-khó
NP-đầy đủ
P
Đáp án khác
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 10, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
3
4
6
Đáp án khác
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 7, b = 5, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 3 lít ở 1 trong 2 bình là bao nhiêu?
4
5
6
Không có phương án nào thực hiện được
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 3, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
2
3
4
5
Đáp án khác
Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:
Đổ nước vào đầy bình 1
Đổ nước vào đầy bình 2
Đổ hết nước từ bình 1 ra ngoài
Đổ hết nước từ bình 2 ra ngoài
Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)
Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)
Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:
B1: Đổ nước vào đầy bình 1
B2: Đổ nước từ bình 1 sang bình 2
B3: Đổ nước vào đầy bình 1
B4: Đổ nước từ bình 1 sang bình 2
ta sẽ thu được 4 lít nước ở bình 1.
Với a = 2, b = 9, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 5 lít ở 1 trong 2 bình là bao nhiêu?
3
4
5
Không có phương án thực hiện
Thuật toán Bellman-Ford tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây?
Đồ thị tổng quát
Đồ thị không chứa chu trình âm
Đồ thị không có cạnh trọng số âm
Đồ thị có hướng không có chu trình DAG
Cây
Đồ thị hai phía
Đáp án khác
Những mệnh đề nào sau đây là ĐÚNG?
Nếu \(A \in NP\)-khó và \(A\prec B\), thì \(B \in NP\)-khó
Nếu \(A \in NP\)-khó và \(B\prec A\), thì \(B \in NP\)-khó
Nếu \(A \in P\) và \(A\prec B\), thì \(B \in P\)
Nếu \(A \in P\) và \(B\prec A\), thì \(B \in P\)
Không đáp án nào đúng
Những phương pháp nào thường được sử dụng để đưa ra lời giải chấp nhận được mà không đảm bảo tính tối ưu trong thời gian đa thức cho bài toán thuộc lớp NP-khó?
Nhánh cận
Tham lam
Chia để trị
Qui hoạch động
Heuristic
Meta-heuristic
Học tăng cường
Thuật toán xấp xỉ
Tất cả các phương pháp liệt kê ở đây
Không đáp án nào đúng
Bài toán người du lịch với yêu cầu tối thiểu hoá chi phí hành trình của người du lịch thuộc lớp bài toán nào?
NP
NP-khó
NP-đầy đủ
P
Đáp án khác
Những phương pháp nào có thể giải bài toán người du lịch cho lời giải chấp nhận được?
Nhánh cận
Tham lam
Qui hoạch động
Heuristic
Meta-heuristic
Học tăng cường
Tất cả các phương pháp trên
Những mối quan hệ nào sau đây là CHẮC CHẮN ĐÚNG?
\(P \subseteq NP\)
\(NPC \subseteq NP\)
\(P \subset NP\)
\(P \neq NP\)
\(P = NP\)
\(NPC = NP\)
\(NPC \subset NP\)
\(NPC \neq NP\)
\(NPC \subset NP\)-khó
\(NP\)-khó \(\cap NP = NPC\)
\(NP \subset NP\)-khó
\(P \neq NP\)-khó
Đáp án khác
Thuật toán Người thu ngân có cho lời giải tối ư với các đồng tiền mệnh giá 1xu, 5xu, 10xu, 25xu và 100xu không?
Có
Không
Cho đồ thị hai phía $G=(X\cup Y, E)$ với $|X|=${m}, $|Y|=${n}, $|E|=${k}, và lực lượng cặp ghép lớn nhất của $G$ là {s}. Hãy tính lực lượng tập độc lập lớn nhất của $G$.
Trong một phiên bản giải thuật quicksort dùng phần tử ở vị trí thứ n/5 làm phần tử chốt. Hỏi độ phức tạp của giải thuật quicksort này trong trường hợp tồi nhất là bao nhiêu?
\(O(nlogn)\)
\(O(n^5logn)\)
\(O(nlog^5n)\)
\(O(n^2)\)
Đáp án khác
Phát biểu nào sau đây về quy lui (backtracking) là đúng?
Bài toán sinh tất cả các xâu nhị phân có độ dài cho trước không thể giải được bằng thuật toán quay lui
Thuật toán quay lui có thể tìm ra giải pháp tối ưu cho bài toán tối ưu hóa tổ hợp
Thuật toán quay lui luôn có độ phức tạp thời gian tính toán đa thức
Thuật toán quay lui không thể tìm thấy bất kỳ lời giải tối ưu nào cho một bài toán tối ưu hóa tổ hợp
Đáp án khác
Cho đồ thị vô hướng G = (V, E), với V là tập đỉnh và E là tập cạnh. Ký hiệu, A[x] là tập các đỉnh kề với đỉnh x, với mọi x thuộc V.
Cho một hàm (được miêu tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào:
process(s, t){
Init an empty queue Q;
for x in V do
d[x] = -1;
Q.push(s);// push an element into the queue Q
d[s] = 0;
while Q not empty do{
u = Q.pop();// pop an element out of the queue Q
for v in A(u) do{
if d[v] = -1 then{
Q.push(v);
d[v] = d[u] + 1;
}
}
}
return d[t];
}
Phát biểu nào dưới đây là đúng?
Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G
Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G
Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G
Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G
Đáp án khác
Cho đoạn chương trình dưới đây (miêu tả bằng mã giả), trong đó mảng a (các phần tử được đánh chỉ số từ 1 tới n), các biến toàn cục (global variables) n, m, T, cnt (a, n, m là tham số đầu vào)
solve(k){
for v = 0 to 1 do{
T = T + v*a[i];
if k = n then{
if T = m then
cnt = cnt + 1;
}else
solve(k+1);
}
}
main{
T = 0;
cnt = 0;
solve(1);
print(cnt);
}
Phát biểu nào dưới đây là đúng?
Chương trình tính số cách chọn các phần tử sao cho tổng các phần tử được chọn bằng m
Chương trình kiểm tra xem tổng các phần tử của a có bằng m không?
Chương trình tính số lần giá trị m xuất hiện trong mảng a
Đáp án khác
Cho đồ thị vô hướng G = (V, E), trong đó V là tập đỉnh và E là tập cạnh. Ký hiệu A[x] là tập các đỉnh kề với đỉnh x (với mọi x thuộc V).
Cho hàm (được mô tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào.
process(s, t){
Init an empty queue Q;
for x in V do
d[x] = -1;
Q.push(s);// push an element into the queue Q
d[s] = 0;
while Q not empty do{
u = Q.pop();// pop an element out of the queue Q
print(u);
for v in A(u) do{
Q.push(v);
d[v] = d[u] + 1;
}
}
return d[t];
}
Phát biểu nào sau đây là đúng?
Đáp án khác
Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều rộng
Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều sâu
Chương trình kết thúc và trả về độ dài (số cạnh) của đường đi ngắn nhất từ s tới t trên G
Cho một cây T = (V, E), trong đó V = {1,2,3,4,5,6,7,8,9,10,11,12,13} là tập các đỉnh và E = {(1,2), (1,12), (1,13), (2,3), (2,4), (3,7), (3,8), (3,9), (4,5), (4,6), (5,10), (5,11)} là tập các cạnh. Các đỉnh 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 lần lượt có trọng số 8, 6, 9, 1, 9, 2, 10, 2, 4, 3, 2, 5, 7. Tìm một tập con S các đỉnh trong V có tổng các trọng số lớn nhất sao cho 2 đỉnh bất kỳ trong S không kề nhau trên T. Tổng các trọng số các đỉnh trong S bằng bao nhiêu?
37
35
38
39
43
45
46
Đáp án khác
Cho đoạn chương trình được miêu tả bởi một đoạn mã giả dưới đây, trong đó hàm P nhận một mảng a, n, W, T, k như tham số (thành phần của mảng a được đánh chỉ số từ 1 tới n) và cnt là một biến toàn cục.
P(a, n, W, T, k){
for v = 0 to 1 do {
if (k = n) then{
if (T + v*a[k] = W) then cnt = cnt + 1;
}else
P(a, n, W, T + v*a[k], k+1);
}
}
Main { // main function
a = {2,3,6,7,4,5}; // array indexed from 1 to 6
cnt = 0;
P(a, 6, 12, 0, 1);
print(cnt); // print the value cnt to the screen
}
Giá trị của cnt được in ra màn hình trong hàm Main là bao nhiêu?4
2
3
5
6
8
9
Đáp án khác
Mỗi phần tử của một Min-Heap (được biểu diễn bởi một cây đầy đủ) có hai trường (id, k), trong đó id là định danh và k là khóa của phần tử. Min-Heap có các hàm (operations) sau:
Hiện hiện một chuỗi các thao tác sau trên Min-Heap:
Phát biểu nào dưới đây là đúng?
Phần tử có định danh 4 là con phải của phần tử có định danh 8
Phần tử có định danh 4 là con trái của phần tử có định danh 8
Phần tử có định danh 2 là con phải của phần tử có định danh 8
Phần tử có định danh 2 là con trái của phần tử có định danh 8
Phần tử có định danh 1 là con phải của phần tử có định danh 7
Phần tử có định danh 1 là con trái của phần tử có định danh 7
Đáp án khác
Hãy ghép cặp thuật toán với bài toán phù hợp.
Thuật toán Dijkstra
Thuật toán Prim
Thuật toán Kruskal
Có thể xây dựng được bao nhiêu đồ thị vô hướng (không nhất thiết phải liên thông) với n đỉnh?
n(n-1)
2n
n!
2(n(n-1)/2
Đáp án khác
Cho đồ thị vô hướng với trọng số \( G \) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \( G \).
Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Xét đồ thị có trọng số \(G\)như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.
Cho đồ thị vô hướng trọng số trên cạnh như dưới đây
Có
Không
Cho đồ thị vô hướng với trọng số trên cạnh như dưới đây
Có
Không
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 14 đỉnh và 30 cạnh đều có bậc là 3 hoặc 5.
Do đó, số đỉnh có bậc là 3 của đồ thị G = {1:NUMERICAL:=5}
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 15 đỉnh và 25 cạnh đều có bậc là 2 hoặc 7.
Do đó, số đỉnh có bậc là 2 của đồ thị G = {1:NUMERICAL:=11}
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 54 cạnh đều có bậc là 3 hoặc 7.
Do đó, số đỉnh có bậc là 3 của đồ thị G = {1:NUMERICAL:=8}
Điền số thích hợp vào chỗ trống:
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 52 cạnh đều có bậc là 4 hoặc 7.
Do đó, số đỉnh có bậc là 4 của đồ thị G = {1:NUMERICAL:=12}
Thuật toán nào dưới đây hiệu quả nhất để tìm đường đi đơn ngắn nhất giữa 2 trong đồ thị tổng quát?
Đáp án khác
Dijkstra
Bellman-Ford
Floyd-Warshall
Prim
Kruskal
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
B
C
D
E
F
Cho đồ thị có hướng như trên hình vẽ:

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:E, D, F, C, B
E, D, C, B, F
E, C, B, F, D
E, C, B, D, F
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị có hướng như trên hình vẽ:

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:E, D, B, F, C
E, D, C, B, F
E, C, B, F, D
E, C, B, D, F
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
B
C
D
E
F
Cho đồ thị có hướng như trên hình vẽ:

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:C, E, B, D, F
C, E, F, D, B
C, F, E, D, B
C, F, E, B, D
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
B
C
D
E
F
Cho đồ thị như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ đỉnh A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
B
C
D
E
F
Cho đồ thị có hướng như trên hình vẽ:

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.
Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?
Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F
B
C
D
E
F
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[6] bằng bao nhiêu?
4
5
6
1
3
Đáp án khác
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[11] bằng bao nhiêu?
4
5
6
1
3
Đáp án khác
Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4,
6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10),
(8,11), (10, 11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:
Hỏi giá trị của Low[10] bằng bao nhiêu?
4
5
6
1
3
Đáp án khác
Hãy xác định đâu là cây tìm kiếm theo chiều sâu xuất phát từ đỉnh 1 (kí hiệu là DFS(1)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.





Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 3 (kí hiệu là DFS(3)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.





Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 2 (kí hiệu là DFS(2)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1, 2 ,3, 4, 5, 6, 7, 8.






Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 4 (kí hiệu là DFS(4)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.





Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 4 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 4 đến đỉnh 7 là:
4 --> 2 --> 5 --> 7
4 --> 5 --> 7
4 --> 2 --> 6 --> 7
4 --> 2 --> 8 --> 6 --> 7
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:
1 --> 4 --> 5 --> 7 --> 6
1 --> 2 --> 6
1 --> 2 --> 8 --> 6
1 --> 2 --> 5 --> 7 --> 6
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:
1 --> 2 --> 4 --> 5 --> 7 -->6
1 --> 2 --> 6
1 --> 2 --> 8 --> 6
1 --> 2 --> 5 --> 7 --> 6
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:
3 --> 4 --> 5 --> 7 -->6
3 --> 1 --> 2 --> 6
3 --> 4 --> 2 --> 6
3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
3 --> 4 --> 2 -->8 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:
2 --> 1 --> 4 --> 5 --> 7
2 --> 8 --> 6 --> 7
2 --> 5 --> 7
2 --> 1 --> 8 --> 6 --> 7
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:
3 --> 1 --> 2 --> 4 --> 5 --> 7 -->6
3 --> 1 --> 2 --> 6
3 --> 4 --> 2 --> 6
3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
3 --> 4 --> 2 -->8 --> 6
Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.
Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:
2 --> 4 --> 5 --> 7
2 --> 8 --> 6 --> 7
2 --> 5 --> 7
2 --> 1 --> 8 --> 6 --> 7
Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 4 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
1 --> 6 --> 4
1 --> 2 --> 5 --> 4
1 --> 3--> 2 --> 5 --> 4
1 --> 5 --> 4
Đáp án khác
Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6, 7} và tập cạnh E ={(1,2), (1,3), (2,4), (2,5), (3,5), (4,6), (4,7), (5, 6), (5, 7), (6, 7)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 6 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
1 --> 2 --> 4 --> 6
1 --> 3 --> 5 --> 7 --> 6
1 --> 3--> 5 --> 6
1 --> 5 --> 7 --> 6
Đáp án khác
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {a, b, c, d, e, f, g} và tập cạnh E ={(a,b), (a,c), (b,d), (b,e), (c,e), (d,f), (d,g), (e, f), (e, g), (f, g)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phải từ đỉnh a (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh a đến đỉnh f trong phép duyệt theo chiều rộng là đường đi nào dưới đây?
a --> b --> d --> f
a --> c --> e --> g --> f
a --> c--> e --> f
a --> e --> g --> f
Đáp án khác
Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 6 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi độ dài đường đi (tính theo số lượng cạnh) từ đỉnh 6 đến đỉnh 3 là bao nhiêu?
2
1
4
5
Đáp án khác
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh s (kí hiệu: BFS(s)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.




Đáp án khác
Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh b (kí hiệu: BFS(b)) trên đồ thị sau:

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.




Đáp án khác
Chúng ta có thể sử dụng các phương pháp tìm kiếm nào dưới đây để tìm tất cả các thành phần liên thông trong đồ thị vô hướng có trọng số G = (V,E, c)?
Tìm kiếm theo chiều rộng (BFS)
Tìm kiếm theo chiều sâu (DFS)
Tìm kiếm theo chiều rộng và chiều sâu
Đáp án khác
Thuật toán nào dưới đây là phù hợp nhất để tìm thành phần liên thông mạnh trong một đồ thị có trọng số?
Thuật toán tìm kiếm theo chiều rộng
Thuật toán tìm kiếm theo chiều sâu
Thuật toán tìm kiếm theo chiều rộng và chiều sâu
Đáp án khác
Thuật toán dijkstra
Tìm đường đi ngắn nhất giữa 2 đỉnh trong đồ thị có hướng không trọng số G = (V, E) thì dùng thuật toán nào dưới đây phù hợp nhất?
Chú ý đường đi ngắn nhất giữa 2 đỉnh là đường đi qua ít cạnh nhất.
Tìm kiếm theo chiều rộng
Tìm kiếm theo chiều sâu
Thuật toán dijkstra
Thuật toán Bellman-Ford
Đáp án khác
Nhận định nào dưới đây là đúng khi so sánh biểu diễn đồ thị theo danh sách kề với biểu diễn đồ thị theo ma trận kề?
Biểu diễn theo danh sách kề sẽ tiết kiệm bộ nhớ hơn cho những ma trận thưa
DFS và BFS có thể thực hiện trong O(V+E) nếu sử dụng biểu diễn theo danh sách kề. Trong khi đó, nếu biểu diễn theo ma trận kề thì các thao tác này có độ phức tạp O(V2). Trong đó V, E lần lượt là số lượng đỉnh và cạnh của đồ thị.
Thêm một đỉnh vào đồ thị sẽ dễ dàng hơn khi biểu diễn theo danh sách kề so với biểu diễn đồ thị theo ma trận kề
Tất cả các đáp án trên
Dãy bậc của một đơn đồ thị là dãy bậc của các đỉnh của đồ thị đó được sắp xếp giảm dần. Dãy nào sau đây không thể là dãy bậc của đồ thị nào đó?
I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2 III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1
II và IV
I và II
III và IV
IV
Đáp án khác
Thuật toán hiệu quả nhất để tìm số lượng các thành phần liên thông trong một đồ thị vô hướng trên n đỉnh và m cạnh có độ phức tạp về thời gian là bao nhiêu?
θ(n)
θ(m)
θ(m + n)
θ(mn)
Đáp án khác
Số lượng cạnh đối đa trong một chu trình trên một đồ thị vô hướng không chu trình gồm n đỉnh là bao nhiêu?
n-1
n
n+1
2n-1
Đáp án khác
Xét một đồ thị có hướng với n đỉnh và m cạnh sao cho tất cả các cạnh đều có trọng số các cạnh bằng nhau. Tìm độ phức tạp của thuật toán đã biết tốt nhất để tính cây khung nhỏ nhất của đồ thị?
O(m+n)
O(m logn)
O(mn)
O(n logm)
Đáp án khác
Gọi G là một đồ thị đơn giản có 20 đỉnh và 8 thành phần liên thông. Nếu chúng ta xóa một đỉnh trong G, thì số thành phần trong G sẽ nằm trong khoảng nào dưới đây?
7 - 19
8-20
8-19
7-20
Đáp án khác
Cấu trúc dữ liệu nào dưới đây phù hợp với duyệt độ thị theo chiều rộng?
Ngăn xếp
Hàng đợi
Danh sách liên kết
Đáp án khác
Để cài đặt thuật toán đường đi ngắn nhất Dijkstra trên đồ thị không có trọng số để nó chạy trong thời gian tuyến tính, cấu trúc dữ liệu sẽ được sử dụng là:
Hàng đợi
Ngăn xếp
Đống (Heap)
B-Tree
Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a.
Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu?
3
4
5
6
Đáp án khác